package org.leetcode.easy.leetcode222;

import org.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
import java.util.regex.Pattern;

public class Solution
{



    public int countNode3(TreeNode root)
    {
        if (root==null)
        {
            return 0;
        }

        return countNodes(root.left) + countNodes(root.right) + 1;
    }


    /**
     * 前序遍历
     */
    public int countNodes2(TreeNode root)
    {
        if (root==null)
        {
            return 0;
        }
        List<TreeNode> list = new ArrayList<>();

        preorder(root.left,list);

        preorder(root.right,list);

        return list.size();
    }

    private void preorder(TreeNode node,List<TreeNode> list)
    {
        if (node==null)
        {
            return;
        }

        list.add(node);
        preorder(node.left,list);
        preorder(node.right,list);
    }




    /**
     * 使用层序遍历
     */
    public int countNodes(TreeNode root) {

        if (root==null)
        {
            return 0;
        }

        int size = 0;

        Deque<TreeNode> deque = new LinkedList<>();

        deque.add(root);

        while (!deque.isEmpty())
        {
            int length = deque.size();

            while (length>0)
            {
                TreeNode tempNode = deque.pop();

                size++;

                if (tempNode.left!=null) deque.add(tempNode.left);
                if (tempNode.right!=null) deque.add(tempNode.right);

                length--;
            }
        }
        return size;
    }

    public static void main(String[] args) {

    }
}
